//为高尔夫比赛砍树
class Solution {
    int m, n;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

public:
    typedef pair<int, pair<int, int>> PIPii;
    typedef pair<int, int> PII;
    int cutOffTree(vector<vector<int>>& forest) {
        m = forest.size();
        n = forest[0].size();
        vector<PIPii> c;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (forest[i][j] > 1)
                    c.push_back({forest[i][j], {i, j}});
        sort(c.begin(), c.end(),
             [](PIPii& x, PIPii& y) { return x.first < y.first; });
        int ret = 0;
        PII start = {0, 0};
        for (int i = 0; i < c.size(); i++) {
            //  cout << c[i].first << ' ';
            PII end = c[i].second;
            bool f = bfs(forest, start, end, ret);
            //  cout << f << endl;
            if (!f) {
                return -1;
            }
            start = end;
        }
        return ret;
    }
    bool bfs(vector<vector<int>>& forest, PII start, PII end, int& ret) {
        if (start == end)
            return true;
        vector<vector<bool>> vis(m, vector<bool>(n, false));
        queue<PII> q;
        int sum = 0;
        q.push(start);
        auto [f, s] = start;
        vis[f][s] = true;
        auto [ef, es] = end;
        while (q.size()) {
            int sz = q.size();
            sum++;
            for (int i = 0; i < sz; i++) {
                auto [a, b] = q.front();
                // cout << "[" << a << ',' << b << "]" << " ";
                q.pop();
                for (int j = 0; j < 4; j++) {
                    int x = a + dx[j];
                    int y = b + dy[j];
                    if (x >= 0 && x < m && y >= 0 && y < n &&
                        forest[x][y] > 0 && !vis[x][y]) {
                        if (x == ef && y == es) {
                            ret += sum;
                            return true;
                        }
                        q.push({x, y});
                        vis[x][y] = true;
                    }
                }
            }
        }
        return false;
    }
};

//